package com.cb2.algorithm.leetcode;

import java.util.HashMap;
import java.util.Map;

/**
 * <a href='https://leetcode.cn/problems/maximum-sum-of-distinct-subarrays-with-length-k'>长度为 K 子数组中的最大和(Maximum Sum of Distinct Subarrays With Length K)</a>
 * <p>给你一个整数数组 nums 和一个整数 k 。请你从 nums 中满足下述条件的全部子数组中找出最大子数组和：
 * <ul>
 *     <li>子数组的长度是 k，且</li>
 *     <li>子数组中的所有元素 各不相同 。</li>
 * </ul>
 * </p>
 * <p>返回满足题面要求的最大子数组和。如果不存在子数组满足这些条件，返回 0 。</p>
 * <p>子数组 是数组中一段连续非空的元素序列。</p>
 *
 * <p>
 * <b>示例：</b>
 * <pre>
 *  示例 1：
 *      输入：nums = [1,5,4,2,9,9,9], k = 3
 *      输出：15
 *      解释：nums 中长度为 3 的子数组是：
 *          - [1,5,4] 满足全部条件，和为 10 。
 *          - [5,4,2] 满足全部条件，和为 11 。
 *          - [4,2,9] 满足全部条件，和为 15 。
 *          - [2,9,9] 不满足全部条件，因为元素 9 出现重复。
 *          - [9,9,9] 不满足全部条件，因为元素 9 出现重复。
 *          因为 15 是满足全部条件的所有子数组中的最大子数组和，所以返回 15 。
 *
 *  示例 2：
 *      输入：nums = [4,4,4], k = 3
 *      输出：0
 *      解释：nums 中长度为 3 的子数组是：
 *          - [4,4,4] 不满足全部条件，因为元素 4 出现重复。
 *          因为不存在满足全部条件的子数组，所以返回 0 。
 * </pre>
 * </p>
 *
 * <p>
 * <b>提示：</b>
 * <ul>
 *     <li>1 <= k <= nums.length <= 10^5</li>
 *     <li>1 <= nums[i] <= 10^5</li>
 * </ul>
 * </p>
 *
 * @author c2b
 * @since 2025/4/30 14:26
 */
public class LC2461MaximumSumOfDistinctSubarraysWithLengthK_M {
    static class Solution {
        public long maximumSubarraySum(int[] nums, int k) {
            Map<Integer, Integer> cntMap = new HashMap<>();
            long sum = 0;
            // 形成窗口
            for (int i = 0; i < k; i++) {
                int val = nums[i];
                sum += val;
                cntMap.put(val, cntMap.getOrDefault(val, 0) + 1);
            }
            // 统计结果
            long res = cntMap.size() == k ? sum : 0;
            // 移动窗口并更新结果
            for (int i = k; i < nums.length; i++) {
                int source = nums[i - k];
                if (cntMap.get(source) == 1) {
                    cntMap.remove(source);
                } else {
                    cntMap.put(source, cntMap.get(source) - 1);
                }
                sum -= source;

                int target = nums[i];
                cntMap.put(target, cntMap.getOrDefault(target, 0) + 1);
                sum += target;

                if (cntMap.size() == k) {
                    res = Math.max(res, sum);
                }
            }
            return res;
        }
    }

    public static void main(String[] args) {
        Solution solution = new Solution();
        System.out.println(solution.maximumSubarraySum(new int[]{1, 5, 4, 2, 9, 9, 9}, 3));
        System.out.println(solution.maximumSubarraySum(new int[]{4, 4, 4}, 3));
    }

}
